package com.xypower.graph;

import java.util.*;
//无环图拓扑排序
public class TopologySort {
    public static List<Node> sortedTopology(Graph graph){
        // Node value：剩余的入度
        HashMap<Node,Integer> inMap = new HashMap<>();
        Queue<Node> zeroInQuere = new LinkedList<>();
        //入度为零的点入队列
        for (Node node:graph.nodes.values()){
            inMap.put(node,node.in);
            if (node.in == 0){
                zeroInQuere.add(node);
            }
        }
        //拓扑排序的结果依次加入 result
        List<Node> result = new ArrayList<>();
        while (!zeroInQuere.isEmpty()){
            Node cur = zeroInQuere.poll();
            result.add(cur);
            for (Node next : cur.nexts){
                inMap.put(next,inMap.get(next) - 1);
                if (inMap.get(next) == 0){
                    zeroInQuere.add(next);
                }
            }
        }
        return result;

    }
}
